#include "assign2d.h"

/**
 * @brief 使用Auction算法获取最大cost/收益的指派
 * @param cost_matrix 假设是一个NxN的方阵，n个customer(row),n个item(cols)，第i行为customer i的出价
 * @param col4row customer对应item,无对应item为-1
 * @param row4col item对应customer,无对应customer为-1
 * @param gain_ 
 * @param max_iter 
 * @return true 
 * @return false 
 */
bool assign2dAuction(const std::vector<std::vector<double>>& cost_matrix,std::vector<int>& col4row,std::vector<int>& row4col,double& gain_,const int max_iter)
{
    bool feasible = false;  // 解是否可行

    size_t N = cost_matrix.size();  // 假设是方阵

    int rows = N;
    int cols = N;

    col4row.clear();
    row4col.clear();

    double eps = 1.0/N;  // 步长

    row4col.resize(cols,-1);  // unassign
    col4row.resize(rows,-1);  // unassign        
    double gain = 0.0f;
    
    int iter = 0;
    // build unassigned customer queue,元素为列索引
    std::queue<int> unassigned_customer = [rows](){std::queue<int> q;for (int i=0;i<rows;i++) q.push(i); return q;}();
    std::vector<double> prices(cols,0);  // 每个item的价格
    while (unassigned_customer.size()!=0)
    {  // if not finished
        int id = unassigned_customer.front();
        unassigned_customer.pop();  // remove from unassigned queue
        // 选择当前未分配item的customer的最大收益
        // float max_profile = 0,submax_profile=0;  // 使用该行只能处理所有cost>0的情况
        double max_profile = -INF,submax_profile=-INF;
        int max_item_ind = -1,submax_item_id=-1;
        std::vector<double> profile(cols,0);
        for (int i=0;i<cols;i++)
        {  // 遍历item获取该id customer对应利润
            // profile[i] = cost_matrix.at<double>(id,i) - prices[i];
            profile[i] = cost_matrix[id][i] - prices[i];
            if (profile[i] > max_profile)
            {  // 如果大于当前收益,则记录最优收益,将原收益变为次优选择
                submax_item_id = max_item_ind;
                submax_profile = max_profile;
                max_profile = profile[i];
                max_item_ind = i;
            }
            else if (profile[i] > submax_profile)
            {  // 如果比当前次优收益高
                submax_item_id = i;
                submax_profile = profile[i];
            }
            else
            {  // 如果小于0或无法超过当前item
                continue;
            }
        }
        // 加价策略
        if (submax_item_id == -1)
        {  // 如果没有次优选择,加价策略为预期最大收益 + eps
            prices[max_item_ind] += profile[max_item_ind] + eps;
        }
        else
        {  // 如果有次优选择,加价策略为预期最大-次大 + eps
            prices[max_item_ind] += profile[max_item_ind] - profile[submax_item_id] + eps;
        }

        // 将已关联到该item的customer添加到未分配队列中
        int assoc_ind = 0;  // 已经关联的customer ind
        for (auto& item:col4row)
        {
            if (item == max_item_ind)
            {  // if assigned 
                item = -1;  // customer 对应item置-1
                unassigned_customer.push(assoc_ind);  // 将冲突的customer加入未分配队列
                // row4col[max_item_ind] = -1;  // max_item_ind不需要操作，后续会设置为当前customer id
                // else{gain -= cost_matrix.at<double>(assoc_ind,max_item_ind);}
                gain -= cost_matrix[assoc_ind][max_item_ind];
            }
            assoc_ind++;
        }
        // 将当前customer竞价选择更新
        row4col[max_item_ind] = id;
        col4row[id] = max_item_ind;
        // else{gain += cost_matrix.at<double>(id,max_item_ind);}
        gain += cost_matrix[id][max_item_ind];

        // stop
        iter++;
        if (iter>max_iter)
        {  // 如果超过迭代次数
            std::cerr<<"Max number of iteration reached! Retry with more than"<<max_iter<<" number of iterations"<<std::endl;
            break;
        }
    }

    if (unassigned_customer.size() == 0){
        feasible = true;
    }

    gain_ = gain;
    return feasible;
}